package 力扣._139_单词拆分;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //字典中的单词可重复使用——》完全背包, 单词之间是有顺序的——》排列——》先容量再物品
        //dp[j]: 0到i结束的串是否可由字典组成
        //dp[j] = dp[j - word[i].len]&&s.sub(j-word[i].len,j)==word[i] || dp[j]
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int j = 0; j <= s.length(); j++) {
            for (int i = 0; i < wordDict.size(); i++) {

                int wordlen = wordDict.get(i).length();
                if (j - wordlen >= 0) {
                    String t = s.substring(j - wordlen, j);
                    dp[j] = (dp[j - wordlen] && t.equals(wordDict.get(i))) || dp[j];
                }
            }
        }
        return dp[s.length()];

    }

    public static void main(String[] args) {
        List<String> wordDict=new LinkedList<>();
        wordDict.add("leet");
        wordDict.add("code");
        new Solution().wordBreak("leetcode",wordDict);
    }
}
